[% setvar title Lazily evaluated list generation functions %]
<div id="archive-notice">
    <h3>This file is part of the Perl 6 Archive</h3>
    <p>To see what is currently happening visit <a href="http://www.perl6.org/">http://www.perl6.org/</a></p>
</div>
<div class='pod'>
<a name='TITLE'></a><h1>TITLE</h1>
<p>Lazily evaluated list generation functions</p>
<a name='VERSION'></a><h1>VERSION</h1>
<pre>  Maintainer: Jeremy Howard &lt;<a href='mailto:j@howard.fm'>j@howard.fm</a>&gt;
  Date: 10 Aug 2000
  Last Modified: 22 Sep 2000
  Mailing List: <a href='mailto:perl6-language-data@perl.org'>perl6-language-data@perl.org</a>
  Number: 81
  Version: 4
  Status: Frozen</pre>
<a name='DISCUSSION'></a><h1>DISCUSSION</h1>
<p>Not surprisingly, the controversial point of discussion for this RFC
was about viability and efficiency of implementation. These points were
more about the use of lazy evaluation in general, rather than generated
lists in particular. The viability of lazy evaluation has been proven
in other languages (both functional and procedural). The efficiency of
generated lists will obviously depend on the implementation, but this
RFC suggests some obvious optimisations for frequently used constructs
(e.g. stepped slices).</p>
<p>The second major point of discussion was around syntax. Other languages
that provide list comprehension do so with quite different syntax (for
example, Haskell and Python v2). However, the syntax is these languages in
not at all Perlish. The proposed syntax incorporates Perl 5 syntax and
extends it using minimal additional notation.</p>
<a name='ABSTRACT'></a><h1>ABSTRACT</h1>
<p>This RFC proposes that the existing <code>..</code> operator produce a lazily
evaluated list. In addition, a new operation <code>:</code> is proposed that allows
for the generation of lazily evaluated lists based on any Perl expression.</p>
<p>This proposal only discusses these operators in a list context. The
current meaning of '..' in a scalar context is not affected.</p>
<a name='CHANGES'></a><h1>CHANGES</h1>
<a name='Since v3'></a><h2>Since v3</h2>
<ul>
<p>Clarified how introspection of list generation parameters would work for
anonymously concatenated lists, and other more complex structures</p>
</ul>
<a name='Since v2'></a><h2>Since v2</h2>
<ul>
<li><a name='Clarified the order of arguments passed to the list generation function'></a>Clarified the order of arguments passed to the list generation function</li>
<li><a name='Made ':' an alias for '..''></a>Made ':' an alias for '..'</li>
</ul>
<a name='Since v1'></a><h2>Since v1</h2>
<ul>
<li><a name='Changed notation to generate lists using previous element value from (@start:&amp;gen:$num_steps) to (@start..&amp;gen:$num_steps)'></a>Changed notation to generate lists using previous element value from
<i>(@start:&amp;gen:$num_steps)</i> to <i>(@start..&amp;gen:$num_steps)</i></li>
<li><a name='Made (@start:&amp;gen:$num_steps) create a list that does not require intermediate values to be calculated'></a>Made <i>(@start:&amp;gen:$num_steps)</i> create a list that does not require
intermediate values to be calculated</li>
</ul>
<a name='DESCRIPTION'></a><h1>DESCRIPTION</h1>
<p>This RFC proposes that Perl incorporate a broader tool box of list
generation techniques:</p>
<ul>
<li><a name='Lazy evaluation of generated lists'></a>Lazy evaluation of generated lists</li>
<li><a name='Generation of arbitrary lists from a function'></a>Generation of arbitrary lists from a function</li>
</ul>
<p>These techniques would allow programs written in Perl to follow a
structure familiar to programmers used to numerical programming
environments. It would provide a more compact notation for many common
mathematical algorithms, and give Perl important information to make key
optimisations.</p>
<a name='Lazy evaluation of generated lists'></a><h2>Lazy evaluation of generated lists</h2>
<p>The <code>..</code> of previous Perls is a <i>list generation operator</i>, which
creates a list based on its parameters:</p>
<pre>  ($start..$stop); # ($start, $start+inc, $start+2*inc, ... $stop)</pre>
<p>where 'inc' is 1 if $start&lt;$stop, or -1 otherwise. The list is generated
as soon as it is declared. These makes some code rather inefficient:</p>
<pre>  @a = (1..1000000);   # One million element list generated here
  print $a[999999];</pre>
<p>creates a one million element list despite only using one element of it.
Under <i>lazy evaluation</i>, elements of the list are only created when they
are required, and saved for later use. In the previous example only
$a[999999] would be calculated by interpolation (not sequentially) and
stored when using lazy evaluation.</p>
<p>Lists, whether generated lazily or not, are assumed to be <i>stable</i>. That
is, the value of $a[999999] will be the same everywhere in a program,
unless @a itself is modified. This means that lazily evaluated lists
provide a handy notation for memoization, as we will see later. It is
proposed that once an element has been calculated in a list, that it is
cached for use later rather than recalculated each time.</p>
<p>Lazy list elements get calculated when they are output, or used in an
expression that is output. If list elements are not output then they are
never calculated.</p>
<a name='Introduction of : to generate arbitrary lists'></a><h2>Introduction of <code>:</code> to generate arbitrary lists</h2>
<p>It is proposed that a new operator be added to Perl's list generation
arsenal, <code>:</code>. The ':' character is chosen because it reflects standard
notation for array slicing, which is an important use of this operator.</p>
<p><code>:</code> is only meaningful when called in a list context, generating a lazily
evaluated list in one of 3 ways.</p>
<ul>
<li><a name='1. ($start..$end:$step)'></a>1. <i>($start..$end:$step)</i></li>
<p>Although earlier Perls could create ascending and descending lists
incrementing by one, other increments required an unwieldy map:</p>
<pre>  @threes = map {3*$_} (1..5);   # (3,6,9,12,15)</pre>
<p>which was also less than intuitive to those used to the simple slicing
notation of numerical programming languages such as Matlab and IDL.</p>
<p>This proposed use of <code>:</code> is identical to <code>..</code> without <code>:</code>, except that
it increments by $step rather than 1. Specifically, returns a list
($start, $start+$step, $start+2*$step, ... $end). If $step does not go
into ($end-$start) exactly, the last element of the list is the largest
number in the series less than or equal to $end.</p>
<p>$step is any non-zero number (not necessarily an integer). $step is
optional--if it's missing then $step is the same as if the <code>:</code> wasn't
there at all. For example:</p>
<pre>  (1..5:2);   # (1,3,5)
  (1..5:);    # Same as (1..5)
  (1..-5:-2);  # (1,-1,-3,-5)
  (1..5:-2);  # () Empty list</pre>
<p>This slicing notation is particularly useful for dealing with arrays,
matrices, and tensors:</p>
<pre>  @matrix = (1,3,4,
             2,6,7);
  @column1of3 = (1..10000:3);   # (1,4,7,...10000)
  print sum(@matrix[@column1of3]);          # Prints 3
  @matrix2 = readBig3ColumnMatrixFromSomewhere();
  $column1Sum = sum(@matrix2[@column1of3]); # No need to redefine our slice!</pre>
<p>Note that more complex slicing, masking, and indirection across
n-dimensional tensors would make the win of not having to respecify the
indexes more substantial than in this simplified example.</p>
<li><a name='2. ($start:$end:$step)'></a>2. <i>($start:$end:$step)</i></li>
<p>An alias for ($start..$end:$step), to keep things familiar for folks
moving over from over languages supporting similar notation.</p>
<li><a name='3. (@start..&amp;gen:$num_steps)'></a>3. <i>(@start..&amp;gen:$num_steps)</i></li>
<p>The most general form of this is to provide a syntax to create bounded or
unbounded lists whose elements are generated by any arbitrary function:</p>
<pre>  ($start, &amp;gen($start), &amp;gen(&amp;gen($start)), {$steps times}...);</pre>
<p>This is created using the notation:</p>
<pre>  ($start..&amp;gen:$steps);</pre>
<p>As before, $start is required (but need not be an integer). The
first argument to &amp;gen is the index of the element being calculated.
For example:</p>
<pre>  @first5PowersOf2 = (1..sub {$_[0]**2}:5);   # (1,2,4,8,16)</pre>
<p>The second argument to &amp;gen is the value of the previous element:</p>
<pre>  @first5PowersOf2 = (1..sub {$_[1]*2}:5);   # (1,2,4,8,16)</pre>
<p>Because lists are memoized automatically, when we later say:</p>
<pre>  print $powersOf2[4];</pre>
<p>The value of $powersOf2[4] is pulled from the memoization cache rather
than recalculated. What's more:</p>
<pre>  print $powersOf2[5];</pre>
<p>is calculated from $powersOf2[4], rather than having to recalculate all
the in-betweens again, because of that caching.</p>
<p>This form of list generation can not generate the Fibonnaci sequence,
because it is not defined by a single $start, and it has more than
one parameter in its generator function. This requires a more
generalised form:</p>
<pre>  ((@start)..&amp;gen:$num_steps)</pre>
<p>which allows us to say:</p>
<pre>  @fib = ((1,1).. ^2 + ^1: 5);   # (1,1,2,3,5)</pre>
<p>if we use the higher-order function notation proposed in RFC 23. As this
example shows, the values of all previous elements are available to the
list generation function as the second and later arguments to the
function. As described earlier, the first argument is the index of the
element being generated.</p>
<li><a name='4. (@start:&amp;gen:$num_steps)'></a>4. <i>(@start:&amp;gen:$num_steps)</i></li>
<p>The <code>(@start..&amp;gen:$num_steps)</code> notation makes it easy to generate lists
that depend on the value of the previous element. For lists where the
element is a direct function of the index, the arguments beyond the first
can simply be ignored:</p>
<pre>  @even_numbers = (1.. ^0 * 2: 5);   # (2,4,6,8,10)</pre>
<p>However, because we want Perl to know how to generate one element of these
lists without having to generate all previous elements, the following
notation is proposed to achieve the same effect:</p>
<pre>  @even_numbers = (1: ^0 * 2: 5);   # (2,4,6,8,10)</pre>
<p>The values of previous elements are not passed to the list generation
function with the ':' syntax. This means that Perl can calculate
directly the value of any element without calculating the value of
previous elements.</p>
<p>This version of a lazily generated list is effectively a memoized function
that restricts its domain to the natural numbers. However it can be used
in some important additional roles--in particular, as a list index:</p>
<pre>  @sub_list = @a[@even_numbers];</pre>
</ul>
<a name='EXTENSIONS'></a><h1>EXTENSIONS</h1>
<p>If infinite lists are available in Perl 6 (see RFC 24), the $num_steps and
$end arguments to the list generation operators can be null. This
indicates that there are infinite elements in the list:</p>
<pre>  @column1of3 = (1.. :3);   # (1,4,7,...)
  @all_even_numbers = (1: ^0 * 2:);   # (2,4,6,8,...)</pre>
<a name='JUSTIFICATION'></a><h1>JUSTIFICATION</h1>
<p>One particularly important use of generated lists is for slicing arrays.
This is difficult in Perl 5, where it is tackled by Perl Data Language
(PDL). Note that currently (perl5) we have to say</p>
<pre>  $n1 = $n-1;  # since we need to stringify
  $y = $x-&gt;slice(&quot;0:$n1:4&quot;);</pre>
<p>This should be contrasted with the less cluttered syntax offered by
numerical Python and commercial systems such as Matlab and IDL:</p>
<pre>  y = x[0:n-1:4];
  </pre>
<p>The syntax in this RFC would provide notation that is familiar to users of
standard numerical programming tools, but is also a natural (and
compatible) step from the existing Perl <code>..</code> operator.</p>
<a name='IMPLEMENTATION'></a><h1>IMPLEMENTATION</h1>
<p>It will be common in numerical programming to see multiple layers of
indirection:</p>
<pre>  @a = (1:5:100000);
  @b = getBigImage();
  @c = @a[@b];
  print $c[5];</pre>
<p>In these cases Perl should consolidate as much as possible at compile time
to avoid too much overhead.</p>
<p>When a lazy list is passed to a function it is not evaluated. The function
can then access only the elements it needs, which are calculated as
required. Furthermore, the arguments that generated the list are available
as attributes of the list, and can therefore be used directly without
actually accessing the list:</p>
<pre>  @a = (1:100000:5);
  ($gen_type) = attributes::get(@a);   # 'increment'
  ($start_val, $end_val, $increment) = attributes::get(@a)[1..3];  # (1, 100000, 5)
  
  @first5PowersOf2 = (1..sub {$_[1]*2}:5);   # (1,2,4,8,16)
  ($gen_type) = attributes::get(@a);   # 'recursive'
  ($start_val, $gen_func, $num_steps) = attributes::get(@a)[1..3];
  
  @even_numbers = (1: ^0 * 2: 5);   # (2,4,6,8,10)
  ($gen_type) = attributes::get(@a);   # 'function'
  ($start_val, $gen_func, $num_steps) = attributes::get(@a)[1..3];  </pre>
<p>For lists that are a combination of these:</p>
<pre>  @b = (1:10:2 , 10:^0*3:30);</pre>
<p>there are two potential ways of allowing introspection of the arguments
that generated the list:</p>
<ul>
<li><a name='Make the attributes a list of lists, where each sublist is the attributes of each concatenated list'></a>Make the attributes a list of lists, where each sublist is the attributes
of each concatenated list</li>
<li><a name='Provide an attribute that returns the actual tokens of the list generation function. These tokens could follow an approach similar to that used in RFC 231.'></a>Provide an attribute that returns the actual tokens of the list
generation function. These tokens could follow an approach similar to
that used in RFC 231.</li>
</ul>
<p>However, if lazy list elements are calculated efficiently on demand, the
need for a programmer to access the list generation parameters at all
should be limited. They are provided to make sure that 'hard things are
possible'.</p>
<a name='REFERENCES'></a><h1>REFERENCES</h1>
<p>RFC 23: Higher-order functions</p>
<p>RFC 24: Semi-finite (lazy) lists</p>
<p>RFC 82: Apply operators component-wise in a list context</p>
<p>RFC 205: New operator ';' for creating array slices</p>
<p>RFC 231: Data: Multi-dimensional arrays/hashes and slices</p>
<p>Memoization in Perl: <a href='http://perl.plover.com/MiniMemoize/' target='_blank'>perl.plover.com</a></p>
<p>List comprehension in Haskell:
<a href='http://www.numeric-quest.com/haskell/hcompanion/principles.html' target='_blank'>www.numeric-quest.com</a>#List
comprehension</p>
<p>Fethi Rabhi and Guy Lapalme:
<i>Algorithms: A functional programming approach</i>,
Addison-Wesley, 235 pages, paperback, 1999. ISBN 0-201-59604-0</p>
<a name='ACKNOWLEDGEMENTS'></a><h1>ACKNOWLEDGEMENTS</h1>
<p>Damian Conway: Reviewed first draft</p>
<p>Karl Glazebrook: Suggested splitting from infinite lists proposal</p>
<p>Christian Soeller: Original 'slice' RFC; suggested argument reordering</p>
<p>Dan Sugalski: Implementation ideas</p>
</div>
